package com.shixianchen.study.day5;

import com.shixianchen.utils.Utils;
import com.shixianjun.sort.Sortable;
import com.shixianjun.sort.SortableElement;

/**
 * @author ShiXianChen
 * @version V1.0.0
 * @Description 希尔排序
 * @date 2022/11/8 22:06
 */
public class ShellSort implements Sortable {


//    @Override
    public void sort1(SortableElement[] arr) {
        int n = arr.length;
        int h = 1;
        while (h <= arr.length / 3){
            h = h*3+1;
        }
        for (int gap = h; gap > 0; gap = (gap-1)/3) {
            //本质是插入排序
            for (int i = gap; i < n; i++) {
                for (int j = i; j > gap - 1; j -= gap) {
                    if (arr[j].value < arr[j - gap].value) {
                        Utils.swap(arr, j, j - 1);
                    }
                }
            }
        }
    }


    @Override
    public void sort(SortableElement[] arr) {
        for (int gap =arr.length /2; gap > 0; gap /=2){
            //希尔排序的本质的插入排序
            for (int i = gap; i < arr.length; i++) {
                //哟插入的数据
                SortableElement insertValue = arr[i];
                int j =  i -gap;
                for (; j >= 0  &&  insertValue.value < arr[j].value; j-=gap) {
                    arr[j+gap] = arr[j];
                }
                arr[j+gap] = insertValue;
            }
        }
    }
}
